/*
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.
*/

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, bool> used;
        for (auto i : num) used[i] = false;
        int maxlen = 0;
        for (auto i : num) {
            if (used[i]) continue;
            int len = 1;
            for (int j = i+1; used.find(j) != used.end(); j++) {
                used[j] = true; len++;
            }
            for (int j = i-1; used.find(j) != used.end(); j--) {
                used[j] = true; len++;
            }
            if (len > maxlen) maxlen = len;
        }
        return maxlen;
    }
};

#if 0
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        int longest_len = 0;
        if (!num.size()) return longest_len;
        unordered_map<int, int> numbers; numbers.clear();
        for (int i = 0; i < num.size(); i++) {
            int n = num[i];
            int len_l = 0, len_r = 0;
            bool l_found = false, r_found = false;
            if (numbers.find(n) != numbers.end()) continue; // duplicate
            if (numbers.find(n-1) != numbers.end()) {
                len_l = numbers[n-1];
                if (-len_l >= -1) l_found = true;
                if (len_l < 0) len_l = -len_l; // 1 or -length
            }
            if (numbers.find(n+1) != numbers.end()) {
                len_r = numbers[n+1];
                if (len_r >= 1) r_found = true;
            }
            if (!l_found && !r_found) {
                numbers[n] = 1; // single-num cluster
            } else if (l_found && !r_found) {
                // merge into left cluster
                numbers[n-len_l] = len_l + 1;
                numbers[n] = -(len_l + 1);
                if (len_l > 1) numbers.erase(n-1);
            } else if (!l_found && r_found) {
                // merge into right cluster
                numbers[n+len_r] = -(len_r + 1);
                numbers[n] = len_r + 1;
                if (len_r > 1) numbers.erase(n+1);
            } else {
                // merge two clusters into one
                int newlen =  len_l + len_r + 1;
                numbers[n-len_l] = newlen;
                numbers[n+len_r] = -newlen;
                if (len_l > 1) numbers.erase(n-1);
                if (len_r > 1) numbers.erase(n+1);
            }
        }
        for (auto it = numbers.begin(); it != numbers.end(); it++) {
            if (it->second > longest_len) longest_len = it->second;
        }
        return longest_len;
    }
};
#endif
